package com.example.demo.java.container.map;

/**
 * 线程安全
 */
public class UDHashTable {

    /** 1、HashTable 问题梳理 (带着问题去看) */
        /* (1)HashTable与HashMap的区别？ */
        /* (2)HashTable与ConcurrentHashMap的区别？ */

    /** 2.常用参数&构造方法 */
              // 位桶
        //    private transient Hashtable.Entry<?, ?>[] table;
              //HashTable条目数总量
        //    private transient int count;
              //下次扩容量
        //    private int threshold;
              //负载因子
        //    private float loadFactor;
              //修改次数
        //    private transient int modCount = 0;
              //默认的构造函数
        //    public Hashtable() {
        //        this(11, 0.75f);
        //    }
              //指定容量大小
        //    public Hashtable(int initialCapacity) {
        //        this(initialCapacity, 0.75f);
        //    }
              //指定容量大小和负载因子大小
        //    public Hashtable(int initialCapacity, float loadFactor) {
                  //指定的容量大小不可以小于0,否则将抛出IllegalArgumentException异常
        //        if (initialCapacity < 0)
        //            throw new IllegalArgumentException("Illegal Capacity: "+
        //                    initialCapacity);
                  //指定的负载因子不可以小于0或为Null，若判定成立则抛出IllegalArgumentException异常
        //        if (loadFactor <= 0 || Float.isNaN(loadFactor))
        //            throw new IllegalArgumentException("Illegal Load: "+loadFactor);
                  //若指定的容量大小为0,则赋为1 即容量初始大小最小为 1
        //        if (initialCapacity==0)
        //            initialCapacity = 1;
        //        this.loadFactor = loadFactor;
                  //声明table实例
        //        table = new HashtableEntry<?,?>[initialCapacity];
                  //下次扩容量长度
        //        threshold = (int)Math.min(initialCapacity, MAX_ARRAY_SIZE + 1);
        //    }
             //传入一个Map集合,将Map集合中元素Map.Entry全部添加进HashTable实例中
        //    public Hashtable(Map<? extends K, ? extends V> t) {
        //        this(Math.max(2*t.size(), 11), 0.75f);
        //        putAll(t);
        //    }

    /** 3.数据结构：单向链表 */
        //    private static class Entry<K, V> implements java.util.Map.Entry<K, V>

    /** 4.hash算法   key.hashCode 与 2^31-1 再与桶的长度取摸 */
        //    int index = (hash & 2147483647) % tab.length;

    /** 5.源码分析
     * (1) 获取 get
     * (2) 存储 put
     * (3) 删除 remove
     * (4) 扩容 reHash   int newCapacity = (oldCapacity << 1) + 1;  *2+1,初始值11
     */

        /** (1) 获取 get */
            //    public synchronized V get(Object key) {
            //        Hashtable.Entry<?, ?>[] tab = this.table;
            //        int hash = key.hashCode();
                      /** 1.计算索引值 */
            //        int index = (hash & 2147483647) % tab.length;
                      /** 2.从当前节点获取存储的key，判断hash与key值是否一直，不一致，将e设置为e.next，继续循环 */
            //        for(Hashtable.Entry e = tab[index]; e != null; e = e.next) {
            //            if (e.hash == hash && e.key.equals(key)) {
            //                return e.value;
            //            }
            //        }
            //        return null;
            //    }

        /** (2) 存储 put */
            //    public synchronized V put(K key, V value) {
            //        if (value == null) {
            //            throw new NullPointerException();
            //        } else {
            //            Hashtable.Entry<?, ?>[] tab = this.table;
            //            int hash = key.hashCode();
            //            int index = (hash & 2147483647) % tab.length;
                          /** 1.如果已存在，则返回旧值，使用新值覆盖 */
            //            for(Hashtable.Entry entry = tab[index]; entry != null; entry = entry.next) {
            //                if (entry.hash == hash && entry.key.equals(key)) {
            //                    V old = entry.value;
            //                    entry.value = value;
            //                    return old;
            //                }
            //            }
                          /** 2.索引位置不存在节点，则新增 */
            //            this.addEntry(hash, key, value, index);
            //            return null;
            //        }
            //    }
            /** 代码快 2.1 增加节点 */
                //      private void addEntry(int hash, K key, V value, int index) {
                //          Hashtable.Entry<?, ?>[] tab = this.table;
                            /** 1.当前存储的数据超过扩容的阈值时，扩容 old * 2 + 1，并重新计算hash */
                //          if (this.count >= this.threshold) {
                //              this.rehash();
                //              tab = this.table;
                //              hash = key.hashCode();
                //              index = (hash & 2147483647) % tab.length;
                //          }
                            /** 2.将数据存储至相应索引位置 */
                //          Hashtable.Entry<K, V> e = tab[index];
                            /** 3.此处采用头插法，新增的节点会在第一个，原来的节点，放到next上 */
                //          tab[index] = new Hashtable.Entry(hash, key, value, e);
                //          ++this.count;
                //          ++this.modCount;
                //      }

        /** (3) 删除 remove */
            //    public synchronized V remove(Object key) {
            //        Hashtable.Entry<?, ?>[] tab = this.table;
            //        int hash = key.hashCode();
                      /** 1.根据hash算法计算索引，获取节点 */
            //        int index = (hash & 2147483647) % tab.length;
            //        Hashtable.Entry<K, V> e = tab[index];
                      /** 2.判断节点的hash与key是否相等，不等时，获取next，继续判断 */
            //        for(Hashtable.Entry prev = null; e != null; e = e.next) {
            //            if (e.hash == hash && e.key.equals(key)) {
                              /** 3.prev不为空意味着头节点不是要删除的，此时将next替换为下一个next节点，进行删除 */
            //                if (prev != null) {
            //                    prev.next = e.next;
            //                } else {
                                  /** 4.删除的节点时索引位置的跟节点，直接将next设置到索引位置 */
            //                    tab[index] = e.next;
            //                }
            //
            //                ++this.modCount;
            //                --this.count;
            //                V oldValue = e.value;
            //                e.value = null;
            //                return oldValue;
            //            }
                          /** 5.没有找到节点，此时，赋值为e(当前的循环节点)，用于删除节点时使用 */
            //            prev = e;
            //        }
            //
            //        return null;
            //    }

        /** (4) 扩容 reHash */
            //    protected void rehash() {
            //        int oldCapacity = this.table.length;
            //        Hashtable.Entry<?, ?>[] oldMap = this.table;
                      /** 1.计算新桶数组的长度   2 * n + 1 */
            //        int newCapacity = (oldCapacity << 1) + 1;
                      /** 2.如果长度超过了int的最大长度，即2的31次幂-1 */
            //        if (newCapacity - 2147483639 > 0) {
            //            if (oldCapacity == 2147483639) {
            //                return;
            //            }
                          /** 3.设置桶长度为int的最大长度 */
            //            newCapacity = 2147483639;
            //        }
                      /** 4.生成新的桶数组并计算扩容阈值 */
            //        Hashtable.Entry<?, ?>[] newMap = new Hashtable.Entry[newCapacity];
            //        ++this.modCount;
            //        this.threshold = (int)Math.min((float)newCapacity * this.loadFactor, 2.14748365E9F);
            //        this.table = newMap;
            //        int i = oldCapacity;
            //
            //        Hashtable.Entry e;
            //        int index;
                      /** 5.遍历旧桶，重新计算索引位置，并设置到新桶 */
            //        while(i-- > 0) {
            //            for(Hashtable.Entry old = oldMap[i]; old != null; newMap[index] = e) {
            //                e = old;
            //                old = old.next;
            //                index = (e.hash & 2147483647) % newCapacity;
            //                e.next = newMap[index];
            //            }
            //        }
            //
            //    }

}
